/*
description : LRU缓存设计 1.0 不考虑扩展功能或线程安全
author : chugehehe
time : 2025-2-18
version : 1
*/

#include <iostream>
#include <list>
#include <unordered_map>
#include <optional>

using std::list;
using std::pair;
using std::unordered_map;
using std::optional;

template <typename Key, typename Value, size_t Capacity>
class LRUCache{
    static_assert(Capacity > 0, "Capacity must be positive .");
    using ListType = list<pair<Key, Value>>;
private:
    ListType _cacheList; // 缓存链表
    unordered_map<Key, typename ListType::iterator> _cacheMap; // 哈希表存储链表索引
    // unordered_map<Key, ListType::iterator> _cacheMap; // error: ListType::iterator解析依赖于k-v，加typename可以告诉编译器这是一个类型(否则也可能是静态成员)
public:
    optional<Value> get(const Key &key) //C++17
    {
        auto it = _cacheMap.find(key);
        if(it == _cacheMap.end()) return std::nullopt;

        //更新链表头 splice(pos, otherList, iterator)
        _cacheList.splice(_cacheList.begin(), _cacheList, it->second);
        return it->second->second;
    }

    // 插入元素（完美转发）
    template <typename K, typename V>
    void put(K&& key, V&& value)
    {
        auto it = _cacheMap.find(key);
        if(it != _cacheMap.end())
        {
            //更新链表头
            it->second->second = std::forward<V>(value);//保持value的右值属性
            _cacheList.splice(_cacheList.begin(), _cacheList, it->second);
            return;
        }

        // 容量满-->淘汰尾部
        if(_cacheMap.size() >= Capacity)
        {
            _cacheMap.erase(_cacheList.back().first);//通过key删除元素
            _cacheList.pop_back();
        }

        //构造新节点到链表头
        //piecewise_construct用于在构造 std::pair 或 std::tuple 时，将参数分别传递给其成员对象的构造函数
        _cacheList.emplace_front(std::piecewise_construct,
        std::forward_as_tuple(std::forward<K>(key)), //将参数打包为tuple 保持右值类别
        std::forward_as_tuple(std::forward<V>(value)));

        _cacheMap.emplace(std::forward<K>(key), _cacheList.begin());
    }
    
    //元素存在性检查
    bool contains(const Key &key) const { return _cacheMap.find(key) != _cacheMap.end(); }

    //当前缓存大小 承诺不抛出异常
    size_t size() const noexcept { return _cacheMap.size(); }

    //清空缓存
    void clear() noexcept  
    {
        _cacheList.clear();
        _cacheMap.clear();
    }
    
};
